package cn.lbd.arithmetic.dp;

class Demo1 {
    public static void main(String[] args) {
        int[] arr = new int[]{3, 34, 4, 12, 5, 2};
        int length = arr.length;
        int target = 14;
        System.out.println(isSumContainArrayElement(arr, length, target));
    }

    /*public static boolean isSumContainArrayElement(int[] arr, int length, int target) {
        if (length == 0) {
            return arr[0] == target;
        } else if (target == 0) {
            return true;
        } else if (arr[length] > target) {
            return isSumContainArrayElement(arr, length - 1, target);
        } else {
            return isSumContainArrayElement(arr,length - 1,target) || isSumContainArrayElement(arr,length - 1,target - arr[length]);
        }
    }*/

    public static boolean isSumContainArrayElement(int[] arr, int length, int target) {
        boolean[][] dp = new boolean[length][target + 1];
        for (int j = 0; j < target + 1; j++) {
            dp[0][j] = false;
        }
        /**
         实际上 dp[0][arr[0]] 就是如果决策到了数组左边界，要判断target剩余长度是否和数组第一个元素相等，是返回true,否则false
         相当于如下代码
         if (length == 0) {
         return arr[0] == target;
         }
         **/
        dp[0][arr[0]] = true;
        for (int i = 0; i < length; i++) {
            dp[i][0] = true;
        }
        for (int i = 1; i < length; i++) {
            for (int j = 1; j < target + 1; j++) {
                if (arr[i] > j) {
                    dp[i][j] = dp[i - 1][j];
                }else {
                    dp[i][j] = dp[i - 1][j] || dp[i - 1][j - arr[i]];
                }
            }
        }
        return dp[length - 1][target];
    }
















}
